import collections


class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        w_set = set()
        first_set = set()
        return_w = ''
        self.flag = True
        for item in words:
            for c in item:
                w_set.add(c)

        def judge(s, p):
            for i in range(min(len(s), len(p))):
                if s[i] != p[i]:
                    return (s[i], p[i])
            if len(s) > len(p):
                self.flag = False
            return None

        for i in range(len(words) - 1):
            t = judge(words[i], words[i + 1])
            if t:
                first_set.add(t)

        if not self.flag:
            return ''
        du_dict = {key: 0 for key in w_set}
        next_dict = collections.defaultdict(set)

        for item in first_set:
            du_dict[item[1]] += 1
            next_dict[item[0]].add(item[1])

        search_w = collections.deque()
        for key in du_dict:
            if du_dict[key] == 0:
                search_w.append(key)
        while search_w:
            w = search_w.popleft()
            return_w += w
            for item in next_dict[w]:
                du_dict[item] -= 1
                if du_dict[item] == 0:
                    search_w.append(item)
        if len(return_w) == len(w_set):
            return return_w
        else:
            return ''


data = Solution()
words = ["wrt", "wrf", "er", "ett", "rftt"]
print(data.alienOrder(words))
words = ["z", "x"]
print(data.alienOrder(words))
words = ["z", "x", "z"]
print(data.alienOrder(words))
words = ["wrt", "wrf"]
print(data.alienOrder(words))
words = ["abc", "ab"]
print(data.alienOrder(words))
words = ["wnlb"]
print(data.alienOrder(words))
words = ["aba"]
print(data.alienOrder(words))
